Pitfall – Undirected Symmetry - Educational Content

Maintaining bidirectional edges in undirected graphs

In undirected graphs, every edge must be represented bidirectionally in adjacency lists. When adding edge {u,v}, you must insert v into u's neighbor list AND insert u into v's neighbor list. Forgetting either direction breaks the graph structure.
The same principle applies to adjacency matrices: they must be symmetric with A[u,v] = A[v,u]. Setting only one direction creates an asymmetric matrix that represents a directed graph instead of the intended undirected one.
Failing to maintain symmetry causes catastrophic errors: degree counts become incorrect, neighbor queries miss connections, and graph traversal algorithms like BFS/DFS may fail to reach all vertices or compute wrong results.
The critical invariant to maintain is: "v ∈ adj[u] if and only if u ∈ adj[v]". This must hold after every add or remove operation. Writing explicit bidirectional code (not assuming it happens automatically) prevents this common bug that can silently corrupt your graph structure.

✗ WRONG (Asymmetric)

Forgetting Symmetry

def add_edge_wrong(adj, u, v):
    adj[u].add(v)
    # Missing: adj[v].add(u)
    ❌ Only adds one direction!

                                    Result: Broken graph

                                    adj['A'] = {'B'}

                                    adj['B'] = {} ← Missing A!
                                

✓ CORRECT (Symmetric)

Maintaining Symmetry

def add_edge_correct(adj, u, v):
    adj[u].add(v)
    adj[v].add(u)
    # Both directions added

                                    Result: Valid graph

                                    adj['A'] = {'B'}

                                    adj['B'] = {'A'} ✓
                                

Wrong Remove Operation

def remove_edge_wrong(adj, u, v):
    adj[u].discard(v)
    # Missing: adj[v].discard(u)
    ❌ Leaves dangling reference!

                                    Problem:

                                    B still thinks it's connected to A

                                    Corrupted graph structure
                                

Correct Remove Operation

def remove_edge_correct(adj, u, v):
    adj[u].discard(v)
    adj[v].discard(u)
    # Both directions removed

                                    Result:

                                    Edge completely removed

                                    No dangling references ✓
                                

Critical Invariant

v ∈ adj[u] ⟺ u ∈ adj[v]

This must hold after every operation.
Violating this invariant means your graph is corrupted.